#include <sys/bitmap.h>
#include <sys/bitops.h>

/*
 * This is a common helper function for find_next_bit and
 * find_next_zero_bit.  The difference is the "invert" argument, which
 * is XORed with each fetched word before searching it for one bits.
 */
static unsigned long _find_next_bit(const unsigned long *addr,
                unsigned long nbits, unsigned long start, unsigned long invert)
{       
        unsigned long tmp;
        
        if (start >= nbits)
                return nbits;
        
        tmp = addr[start / BITS_PER_LONG] ^ invert;
        
        /* Handle 1st word. */
        tmp &= BITMAP_FIRST_WORD_MASK(start);
        start = rounddown(start, BITS_PER_LONG);
        
        while (!tmp) {
                start += BITS_PER_LONG;
                if (start >= nbits)
                        return nbits;
                
                tmp = addr[start / BITS_PER_LONG] ^ invert;
        }
        
        return min(start + __ffs(tmp), nbits);
}

/*
 * Find the next set bit in a memory region.
 */
unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
                            unsigned long offset)
{
        return _find_next_bit(addr, size, offset, 0UL);
}

unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
                                 unsigned long offset)
{
        return _find_next_bit(addr, size, offset, ~0UL);
}

/*
 * Find the first set bit in a memory region.
 */
unsigned long find_first_bit(const unsigned long *addr, unsigned long size)
{       
        unsigned long idx;
        
        for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
                if (addr[idx]) 
                        return min(idx * BITS_PER_LONG + __ffs(addr[idx]), size);
        }
        
        return size;
}

/*
 * Find the first cleared bit in a memory region.
 */
unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size)
{
        unsigned long idx;

        for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
                if (addr[idx] != ~0UL)
                        return min(idx * BITS_PER_LONG + ffz(addr[idx]), size);
        }

        return size;
}

unsigned long find_last_bit(const unsigned long *addr, unsigned long size)
{
        if (size) {
                unsigned long val = BITMAP_LAST_WORD_MASK(size);
                unsigned long idx = (size-1) / BITS_PER_LONG;

                do {
                        val &= addr[idx];
                        if (val)
                                return idx * BITS_PER_LONG + __fls(val);

                        val = ~0ul;
                } while (idx--);
        }
        return size;
}
